package stack

func longestPalindrome(s string) string {

	helper := func(left, right int, s string) (int, int) {
		for left >= 0 && right < len(s) && s[left] == s[right] {
			left--
			right++
		}
		return left + 1, right - 1
	}

	maxLen := 1
	left, right := 0, 0

	for i := 0; i < len(s); i++ {
		l1, r1 := helper(i, i, s)
		l2, r2 := helper(i, i+1, s)
		if r1-l1+1 > maxLen {
			maxLen = r1 - l1 + 1
			left, right = l1, r1
		}
		if r2-l2+1 > maxLen {
			maxLen = r2 - l2 + 1
			left, right = l2, r2
		}
	}
	return s[left : right+1]
}

func longestPalindrome2(s string) string {
	if len(s) == 0 {
		return s
	}

	dp := make([][]bool, len(s))
	for i := range dp {
		dp[i] = make([]bool, len(s))
		for j := range dp[i] {
			dp[i][j] = true
		}
	}

	maxLen := 1
	left, right := 0, 0

	for j := 0; j < len(s); j++ {
		for i := 0; i < j; i++ {
			if s[i] != s[j] {
				dp[i][j] = false
			} else {
				dp[i][j] = dp[i+1][j-1]
				if dp[i][j] && j-i+1 > maxLen {
					maxLen = j - i + 1
					left, right = i, j
				}
			}
		}
	}

	return s[left : right+1]
}
